package com.future;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.stream.Collectors;

/**
 * Description:
 * 思路可参考：Code02_CoinsWayEveryPaperDifferent
 * 给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
 * <p>
 * candidates 中的每个数字在每个组合中只能使用 一次 。
 * <p>
 * 注意：解集不能包含重复的组合。 
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/combination-sum-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author weiruibai.vendor
 * Date: 2022/2/19 22:44
 */
public class Solution_40 {

    public static void main(String[] args) {

        Set<List<Integer>> set = new HashSet<>();
        List<Integer> l1 = new ArrayList<Integer>() {{
            add(1);
            add(34);
            add(15);
            add(10);
        }};
        List<Integer> l2 = new ArrayList<Integer>() {{
            add(1);
            add(34);
            add(15);
            add(10);
        }};
        set.add(l1);
        set.add(l2);
        System.out.println(set);
        int[] candidates = {2, 5, 2, 1, 2};
        candidates = new int[]{1, 2, 3, 4, 5};
        //candidates = new int[]{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
        int target = 5;
        target = 7;
        // [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
        //target = 27;

        //combinationSum2(candidates, target);
        combinationSum2_2(candidates, target);
    }

    static List<int[]> freq = new ArrayList<int[]>();
    static List<List<Integer>> ans = new ArrayList<List<Integer>>();
    static List<Integer> sequence = new ArrayList<Integer>();

    public static List<List<Integer>> combinationSum2_2(int[] candidates, int target) {
        Arrays.sort(candidates);
        for (int num : candidates) {
            int size = freq.size();
            if (freq.isEmpty() || num != freq.get(size - 1)[0]) {
                freq.add(new int[]{num, 1});
            } else {
                ++freq.get(size - 1)[1];
            }
        }
        dfs(0, target);
        return ans;
    }

    public static void dfs(int pos, int rest) {
        if (rest == 0) {
            ans.add(new ArrayList<Integer>(sequence));
            return;
        }
        if (pos == freq.size() || rest < freq.get(pos)[0]) {
            return;
        }

        dfs(pos + 1, rest);

        int most = Math.min(rest / freq.get(pos)[0], freq.get(pos)[1]);
        for (int i = 1; i <= most; ++i) {
            sequence.add(freq.get(pos)[0]);
            dfs(pos + 1, rest - i * freq.get(pos)[0]);
        }
        for (int i = 1; i <= most; ++i) {
            sequence.remove(sequence.size() - 1);
        }
    }

    /**
     * 暴力方法：超时
     *
     * @param candidates
     * @param target
     * @return
     */
    public static List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        if (candidates == null || candidates.length == 0 || target <= 0) {
            return ans;
        }
        List<List<Integer>> process = process(candidates, 0, target, ans, new HashMap<>());
        process.forEach(l -> l.sort(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        }));
        Set<List<Integer>> notRepeatList = new HashSet<>();
        notRepeatList.addAll(process);
        return notRepeatList.stream().collect(Collectors.toList());
    }


    private static List<List<Integer>> process(int[] candidates, int L, int rest, List<List<Integer>> ans, Map<Integer, Integer> map) {
        remove(L, map);
        if (rest == 0) {
            remove(L, map);
            List<Integer> res = new ArrayList<Integer>() {{
                addAll(map.values());
            }};
            ans.add(res);
            return ans;
        }
        if (rest < 0) {
            remove(L - 1, map);
            return ans;
        }
        if (L == candidates.length) {
            remove(L - 1, map);
            return ans;
        }
        process(candidates, L + 1, rest, ans, map);
        map.put(L, candidates[L]);
        process(candidates, L + 1, rest - candidates[L], ans, map);
        return ans;
    }

    /**
     * 重点
     * 跳出的递归，需要手动移除超出当前操作的下标
     *
     * @param L
     * @param map
     */
    private static void remove(int L, Map<Integer, Integer> map) {
        if (!map.isEmpty()) {
            List<Integer> collect = map.keySet().stream().filter(obj -> obj >= L).collect(Collectors.toList());
            for (Integer removeIndex : collect) {
                map.remove(removeIndex);
            }
        }
    }

    public static int coinWays(int[] arr, int aim) {
        return pro(arr, 0, aim);
    }

    private static int pro(int[] arr, int index, int rest) {
        if (index == arr.length) {
            return rest == 0 ? 1 : 0;
        }
        if (rest < 0) {
            return 1;
        }
        return pro(arr, index + 1, rest) + pro(arr, index + 1, rest - arr[index]);
    }
}
